package number_operatation.leetcode.easy;

/**
 * @author bruin_du
 * @description 比特位计数
 * @date 2022/9/16 23:51
 **/
public class Num338_CountBits {
    public int[] countBits(int n) {
        // 方法一：老土的计算每一位数的1的个数
        // 时间复杂度：O(n*log(n))
        method1(n);

        // 方法二：奇偶情况分离，动态规划
        // 时间复杂度：O(n)
        return method2(n);
    }

    private int[] method1(int n) {
        int[] res = new int[n + 1];
        for (int i = n; i >= 0; i--) {
            int count = 0, num = i;
            while (num != 0) {
                num &= num - 1;
                count++;
            }
            res[i] = count;
        }
        return res;
    }

    private int[] method2(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i < res.length; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}
